题面

好难表述啊~

在n*m的矩阵上，有一些大兵（为0），一些空地（一个正整数），障碍物（-1），现在摧毁一些空地，使所有大兵不能走出矩阵去（代价为表示空地的整数），求最小代价

思路：

网络流最小割

“阻止”，“最小”，看到这样的字眼，肯定就要想到最小割啊

在互相能到达的点之间建边，容量为INF，因为——它不能炸……

然后把每个点拆成入点和出点，每个兵所在的出点和源点S直接相连，在最外面的点的出点和汇点T直接相连

最后套模板，OK了

最重要的还是建边，能够理解题目的意思，想出对应的策略

Code：

#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define M 5010
#define N 2010
#define Mn 31
using namespace std;
int Cx[4]={1,0,0,-1};//预处理移动的方向
int Cy[4]={0,1,-1,0};
struct node{
    int to,cap;
    int nxt;
    node(int a,int b):to(a),cap(b){    }
    node(){    }
}b[M<<1];
int head[N],deep[N],a[Mn][Mn];
int n,m,S,T,Maxflow,Max,t=1;
bool p[Mn][Mn];
int read()
{
    int s=0,p=1;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            p=-1;
        c=getchar();
    }
    while(isdigit(c))
    {
        s=(s<<1)+(s<<3)+c-'0';
        c=getchar();
    }
    return s*p;
}
int Cag(int x,int y)
{
    return (x-1)*m+y;
}
void add(int x,int y,int cap)
{
    b[++t]=node(y,cap);
    b[t].nxt=head[x];
    head[x]=t;
    b[++t]=node(x,0);
    b[t].nxt=head[y];
    head[y]=t;
    return;
}
void Add(int x,int y)
{
    int Tx,Ty;
    for(int i=0;i<4;i++)
    {
        Tx=x+Cx[i];Ty=y+Cy[i];
        if(p[Tx][Ty])//边框的用处
            add(Cag(x,y)+Max,T,INF);//在矩阵外就和汇点T相连
        else
            add(Cag(x,y)+Max,Cag(Tx,Ty),INF);//否则出点和入点相连
    }
    return;
}
bool BFS()
{
    int i,cur;
    int to,cap;
    queue<int>p;
    memset(deep,0,sizeof(deep));
    p.push(S);deep[S]=1;
    while(!p.empty())
    {
        cur=p.front();p.pop();
        for(i=head[cur];i;i=b[i].nxt)
        {
            to=b[i].to;cap=b[i].cap;
            if(cap&&!deep[to])
            {
                deep[to]=deep[cur]+1;
                p.push(to);
                if(to==T)
                    return 1;
            }
        }
    }
    return 0;
}
int Dinic(int k,int flow)
{
    if(k==T)
        return flow;
    int i,to,cap,res,rest=flow;
    for(i=head[k];i&&rest;i=b[i].nxt)
    {
        to=b[i].to;cap=b[i].cap;
        if(cap&&deep[to]==deep[k]+1)
        {
            res=Dinic(to,min(rest,cap));
            if(!res)
                deep[to]=0;
            b[i].cap-=res;
            b[i^1].cap+=res;
            rest-=res;
        }
    }
    return flow-rest;
}
int main()
{
    int i,j,flow;
    n=read();m=read();
    Max=n*m;T=Max+Max+1;//汇点T
    for(i=1;i<=n;i++)//裱个框，方便判断
        p[i][0]=p[i][m+1]=1;
    for(i=1;i<=m;i++)
        p[0][i]=p[n+1][i]=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            a[i][j]=read();
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(a[i][j]==-1)//如果是障碍就不建边
                continue;
            if(a[i][j]==0)//如果是大兵就与源点建边，注意，是出点！否则都要为zero了……
                add(S,Cag(i,j)+Max,INF);
            else//如果是空地，那么在自己的入点和出点之间建边
                add(Cag(i,j),Cag(i,j)+Max,a[i][j]);//注意，这里的容量是a[i][j]，就是要炸多少次
            Add(i,j);//放个函数里看看能不能和四周相连
        }
    while(BFS())//Dinic模板
        while((flow=Dinic(S,INF)))
            Maxflow+=flow;
    printf("%d",Maxflow);
    return 0;
}

推荐题目

Luogu P2472 [SCOI2007]蜥蜴

有点类似，但很不相同！

devil.